{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotate Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #轮转数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>，将数组中的元素向右轮转 <code>k</code><em>&nbsp;</em>个位置，其中&nbsp;<code>k</code><em>&nbsp;</em>是非负数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,5,6,7], k = 3\n",
    "<strong>输出:</strong> <code>[5,6,7,1,2,3,4]</code>\n",
    "<strong>解释:</strong>\n",
    "向右轮转 1 步: <code>[7,1,2,3,4,5,6]</code>\n",
    "向右轮转 2 步: <code>[6,7,1,2,3,4,5]\n",
    "</code>向右轮转 3 步: <code>[5,6,7,1,2,3,4]</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,-100,3,99], k = 2\n",
    "<strong>输出：</strong>[3,99,-1,-100]\n",
    "<strong>解释:</strong> \n",
    "向右轮转 1 步: [99,-1,-100,3]\n",
    "向右轮转 2 步: [3,99,-1,-100]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>尽可能想出更多的解决方案，至少有 <strong>三种</strong> 不同的方法可以解决这个问题。</li>\n",
    "\t<li>你可以使用空间复杂度为&nbsp;<code>O(1)</code> 的&nbsp;<strong>原地&nbsp;</strong>算法解决这个问题吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotate-array](https://leetcode.cn/problems/rotate-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotate-array](https://leetcode.cn/problems/rotate-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7]\\n3', '[-1,-100,3,99]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        arraylength = len(nums)\n",
    "        k = k % arraylength\n",
    "        if k == 0 or k == arraylength:\n",
    "            return nums\n",
    "\n",
    "        nums[:] = nums[-k:] + nums[:len(nums) - k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        k = k%len(nums)\n",
    "        def arrReverse(arr, start, end):\n",
    "            mid = (end-start+1) // 2 \n",
    "            for i in range(mid):\n",
    "                arr[start+i] ^= arr[end-i]\n",
    "                arr[end-i] ^= arr[start+i]\n",
    "                arr[start+i] ^= arr[end-i]\n",
    "        \n",
    "        arrReverse(nums, 0, len(nums)-1-k)\n",
    "        arrReverse(nums, len(nums)-k, len(nums)-1)\n",
    "        arrReverse(nums, 0, len(nums)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)\n",
    "        nums_new = nums[-k:] + nums[:len(nums) - k]\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums_new[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        while(k>0):\n",
    "            i = nums.pop()\n",
    "            nums.insert(0,i)\n",
    "            k-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        k = l - k % l\n",
    "        nums[:] = nums[k:] + nums[0:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: 'List[int]', k: 'int') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        lens = len(nums)\n",
    "        k = k%lens\n",
    "        # print('k=',k)\n",
    "        nums[:] = k * [0] + nums\n",
    "        # print(nums)\n",
    "        nums[0:k] = nums[lens:k+lens]\n",
    "        # print(nums)\n",
    "        nums[:]=nums[0:lens]\n",
    "        # print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k_value = k % length\n",
    "\n",
    "        # 将元素移动到新位置与原有元素组成二元列表\n",
    "        s = length - 1\n",
    "        for i in range(len(nums)):\n",
    "            if type(nums[i]) != list:\n",
    "                nums[k_value - s - 1] = [nums[i], nums[k_value - s - 1]]\n",
    "            else:\n",
    "                nums[k_value - s - 1] = [nums[i].pop(), nums[k_value - s - 1]]\n",
    "\n",
    "            s -= 1\n",
    "\n",
    "        # 将所有列表类型元素还原为数字\n",
    "        for j in range(length):\n",
    "            nums[j] = nums[j][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        length=len(nums)\n",
    "        temp=[0]*length\n",
    "        print(length)\n",
    "        for i in range(length):\n",
    "            print(nums[i])\n",
    "            temp[(i+k)%length]=nums[i]\n",
    "        for j in range(length):\n",
    "            nums[j]=temp[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        while i<k:\n",
    "            s = nums.pop()\n",
    "            nums.insert(0,s)\n",
    "            i=i+1\n",
    "        for i in nums:\n",
    "            print(i)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: 'List[int]', k: 'int') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def rotateIndex(i):\n",
    "            return (i+k)%len(nums)\n",
    "        \n",
    "        k = k% len(nums)\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            current = i\n",
    "            prev = nums[i]\n",
    "\n",
    "            while True:\n",
    "                next = rotateIndex(current)\n",
    "                tmp = prev\n",
    "                prev = nums[next]\n",
    "                nums[next] = tmp\n",
    "                current = next\n",
    "                count+=1\n",
    "                if i == current:\n",
    "                    break\n",
    "            \n",
    "            if count >= len(nums):\n",
    "                break\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        k=k%n\n",
    "        def swap(l,r):\n",
    "            while(l<r):\n",
    "                nums[l],nums[r]=nums[r],nums[l]\n",
    "                l=l+1\n",
    "                r=r-1\n",
    "        swap(0,n-k-1)\n",
    "        swap(n-k,n-1)\n",
    "        swap(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        if len(nums) == 1 or k == 0 :\n",
    "            nums = nums\n",
    "        else:\n",
    "            nums[:] = nums[-k:] + nums[:len(nums)-k]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        start = 0\n",
    "        end = len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n",
    "        start = 0\n",
    "        end = k%len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n",
    "\n",
    "        start = k%len(nums)\n",
    "        end = len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k = k%length\n",
    "        start = 0\n",
    "        count = 0\n",
    "        while count < length:\n",
    "            cur_index = start\n",
    "            pre = nums[cur_index]\n",
    "            while True:\n",
    "                next_index = (cur_index+k)%length\n",
    "                temp = nums[next_index]\n",
    "                nums[next_index] = pre\n",
    "                pre = temp\n",
    "                cur_index = next_index\n",
    "                count += 1\n",
    "                if cur_index == start:\n",
    "                    break\n",
    "            start +=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        a= [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            a[(i+k)%len(nums)] = nums[i]\n",
    "        nums[:] = a[:]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        csr = nums[0]\n",
    "        buf = []\n",
    "        for _ in range(len(nums)):\n",
    "            # print(buf, idx)\n",
    "            if idx in buf:\n",
    "                idx = 0\n",
    "                while idx in buf:\n",
    "                    idx += 1\n",
    "                    csr = nums[idx]\n",
    "            # print(\"new idx: \", idx, \"csr: \", csr)\n",
    "\n",
    "            buf.append(idx)\n",
    "            idx += k\n",
    "            idx %= len(nums)\n",
    "\n",
    "            nums[idx], csr = csr, nums[idx]\n",
    "            # print(nums)\n",
    "            # print(\"--------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        csr = nums[0]\n",
    "        buf = []\n",
    "        for _ in range(len(nums)):\n",
    "            # print(buf, idx)\n",
    "            if idx in buf:\n",
    "                # idx = 0\n",
    "                # while idx in buf:\n",
    "                    idx += 1\n",
    "                    csr = nums[idx]\n",
    "            # print(\"new idx: \", idx, \"csr: \", csr)\n",
    "\n",
    "            buf.append(idx)\n",
    "            idx += k\n",
    "            idx %= len(nums)\n",
    "\n",
    "            nums[idx], csr = csr, nums[idx]\n",
    "            # print(nums)\n",
    "            # print(\"--------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        nums[:] = nums[-k :] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        temp = list(nums)\n",
    "        lenth = len(nums)\n",
    "        for i in range(lenth):\n",
    "            nums[(i + k) % lenth] = temp[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        k = k % n   #当k大于数组长度n时，移动k次等于移动k%n次\n",
    "        def reverse(nums, i, j):\n",
    "            left, right = i, j - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        reverse(nums, 0, n-k)\n",
    "        reverse(nums, n-k, n)\n",
    "        reverse(nums, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k = k%length\n",
    "        if k==0:\n",
    "            return nums\n",
    "        iterset = set(range(k))\n",
    "        while(iterset):\n",
    "            idx = iterset.pop()\n",
    "            temp = nums[idx]\n",
    "            while(True):\n",
    "                while(idx+k<length):\n",
    "                    temp,nums[idx+k] = nums[idx+k],temp\n",
    "                    idx+=k\n",
    "                temp,nums[(idx+k)%length] = nums[(idx+k)%length],temp\n",
    "                if (idx+k)%length in iterset:\n",
    "                    iterset.remove((idx+k)%length)\n",
    "                    idx = (idx+k)%length\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        temp = {}\n",
    "        total = len(nums)\n",
    "        i = 0\n",
    "        while i < total:\n",
    "            j = (i + k) % total\n",
    "            temp[j] = nums[j]\n",
    "            if i in temp:\n",
    "                nums[j] = temp.pop(i)\n",
    "            else:\n",
    "                nums[j] = nums[i]\n",
    "            i += 1            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n<=1:\n",
    "            return\n",
    "\n",
    "        k = k%n\n",
    "\n",
    "        def move(start, step):\n",
    "            pre = start\n",
    "            startval = nums[start]\n",
    "            nextind = pre - step\n",
    "            nextind = n + nextind if nextind < 0 else nextind\n",
    "\n",
    "            while nextind != start:\n",
    "                if pre in state:\n",
    "                    state[pre] = True\n",
    "                nums[pre] = nums[nextind]\n",
    "                pre = nextind\n",
    "                nextind = pre - step\n",
    "                nextind = n + nextind if nextind < 0 else nextind\n",
    "            nums[pre] = startval\n",
    "\n",
    "        state = {i:False for i in range(k)}\n",
    "        for i in range(k):\n",
    "            if not state[i]:\n",
    "                move(i, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        done_index = set()\n",
    "        done_index.add(0)\n",
    "        count, index, temp = 1, 0, nums[0]\n",
    "        while count <= n:\n",
    "            index = (index + k) % n\n",
    "            count += 1\n",
    "            temp, nums[index] = nums[index], temp\n",
    "            if index in done_index:\n",
    "                if index + 1 < n:\n",
    "                    index += 1\n",
    "                    temp = nums[index]\n",
    "            done_index.add(index)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return\n",
    "        shift = k % len(nums)\n",
    "        if shift == 0:\n",
    "            return\n",
    "        shift_index_set = set([])\n",
    "        print(shift)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            currect_index = i\n",
    "            current_v = nums[currect_index]\n",
    "            while True:\n",
    "                if currect_index not in shift_index_set:\n",
    "                    next_index = (currect_index + shift) % len(nums)\n",
    "                    tmp = nums[next_index]\n",
    "                    nums[next_index] = current_v\n",
    "                    current_v = tmp\n",
    "                    shift_index_set.add(currect_index)\n",
    "                    print(next_index, currect_index, current_v)\n",
    "                    currect_index = next_index\n",
    "                else:\n",
    "                    break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        length = len(nums)\n",
    "        index = 0\n",
    "        n = nums[index]\n",
    "        while len(visited) < length:\n",
    "            while index not in visited:\n",
    "                new = (index + k) % length\n",
    "                n, nums[new] = nums[new], n\n",
    "                visited.add(index)\n",
    "                index = new\n",
    "            index = (index + 1) % length\n",
    "            n = nums[index]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        hold = nums[0]\n",
    "        temp = 0\n",
    "        index = 0\n",
    "        i = 0\n",
    "        flag = set([])\n",
    "\n",
    "        while i < l:\n",
    "            index = (index+k)%l\n",
    "            i += 1\n",
    "            if index in flag:\n",
    "                index = (index+1)%l\n",
    "                hold = nums[index]\n",
    "                i -= 1\n",
    "            else:\n",
    "                temp = nums[index]\n",
    "                nums[index] = hold\n",
    "                hold = temp\n",
    "                flag.add(index)\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        # b = nums[(len(nums) - k):]\n",
    "        # for i in range(len(b)-1, -1, -1):\n",
    "        #     nums.pop()\n",
    "        #     nums.insert(0, b[i])\n",
    "        class Node(object):\n",
    "            def __init__(self, value=None, prev=None, next=None):\n",
    "                self.value, self.prev, self.next = value, prev, next\n",
    "\n",
    "        class CircualDoubleLinedList(object):\n",
    "            def __init__(self, maxsize=None):\n",
    "                self.maxsize = maxsize\n",
    "                node = Node()\n",
    "                node.next, node.prev = node, node\n",
    "                self.root = node\n",
    "                self.length = 0\n",
    "            \n",
    "            def __len__(self):\n",
    "                return self.length\n",
    "\n",
    "            def headnode(self):\n",
    "                return self.root.next\n",
    "\n",
    "            def tailnode(self):\n",
    "                return self.root.prev\n",
    "                \n",
    "            def append(self, value):\n",
    "                if self.maxsize is not None and len(self) > self.maxsize:\n",
    "                    raise Exception('full')\n",
    "                node = Node(value=value)\n",
    "                tailnode = self.tailnode()\n",
    "\n",
    "                tailnode.next = node\n",
    "                node.prev = tailnode\n",
    "\n",
    "                node.next = self.root\n",
    "                self.root.prev = node\n",
    "\n",
    "                self.length += 1\n",
    "            \n",
    "            def appendleft(self, value):\n",
    "                if self.maxsize is not None and len(self) > self.maxsize:\n",
    "                    raise Exception('full')\n",
    "                \n",
    "                node = Node(value=value)\n",
    "                if self.root.next is self.root:\n",
    "                    node.next = self.root\n",
    "                    node.prev = self.root\n",
    "\n",
    "                    self.root.next = node\n",
    "                    self.root.prev = node\n",
    "                else:\n",
    "                    node.prev = self.root\n",
    "                    headnode = self.root.next\n",
    "                    node.next = headnode\n",
    "                    headnode.prev = node \n",
    "                    self.root.next = node\n",
    "                self.length += 1\n",
    "            \n",
    "            def remove(self, node):\n",
    "                if node is self.root:\n",
    "                    return\n",
    "                else:\n",
    "                    node.prev.next = node.next\n",
    "                    node.next.prev = node.prev\n",
    "            \n",
    "            def iter_node(self):\n",
    "                if self.root.next is self.root:\n",
    "                    return\n",
    "                curnode = self.root.next\n",
    "                while curnode.next is not self.root:\n",
    "                    yield curnode\n",
    "                    curnode = curnode.next\n",
    "                yield curnode\n",
    "            \n",
    "            def __iter__():\n",
    "                for node in self.iter_node():\n",
    "                    yield node.value\n",
    "            \n",
    "            def iter_node_reverse(self):\n",
    "                if self.root.prev is self.root:\n",
    "                    return Node()\n",
    "                \n",
    "                curnode = self.root.prev\n",
    "                while curnode.prev is not self.root:\n",
    "                    yield curnode\n",
    "                    curnode = curnode.prev\n",
    "                yield curnode\n",
    "            \n",
    "            def move_root(self, node_head):\n",
    "                self.root.next = node_head\n",
    "                self.root.prev = node_head.prev\n",
    "                node_head.prev.next = self.root\n",
    "                node_head.prev = self.root\n",
    "\n",
    "        if len(nums)!=0 and k !=0 and len(nums)!= k and len(nums)!=1:    \n",
    "            k = k%len(nums)\n",
    "            # k -= 1\n",
    "            doublelist_nums = CircualDoubleLinedList()\n",
    "            for i in nums:\n",
    "                doublelist_nums.append(i)\n",
    "            before_tail = doublelist_nums.tailnode()\n",
    "            before_head = doublelist_nums.headnode()\n",
    "            new_head = Node()\n",
    "            for node in doublelist_nums.iter_node_reverse():\n",
    "                if k > 0:\n",
    "                    new_head = node\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    break\n",
    "            before_tail.next = before_head\n",
    "            before_head.prev = before_tail\n",
    "            doublelist_nums.move_root(new_head)\n",
    "            doublist = [node.value for node in doublelist_nums.iter_node()]\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] = doublist[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        n = len(nums)\n",
    "        step = k % n\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while count < n:\n",
    "            j = i\n",
    "            temp = nums[i]\n",
    "            nums[(i + step) % n], temp = temp, nums[(i + step) % n]\n",
    "            count += 1\n",
    "            i = (i + step) % n\n",
    "            while j != i and count < n:\n",
    "                nums[(i + step) % n], temp = temp, nums[(i + step) % n]\n",
    "                count += 1\n",
    "                i = (i + step) % n\n",
    "            if count == n:\n",
    "                break\n",
    "            i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        nums[:] = nums[-k:]+nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        n = len(nums)\n",
    "        while k > n:\n",
    "            k = k -n\n",
    "        i = n -k\n",
    "        list1= nums[n-k:n]\n",
    "        list2 = nums[0:n-k]\n",
    "        for l in range(len(list2)):\n",
    "            nums[l+k] = list2[l]\n",
    "        for j in range(len(list1)):\n",
    "            nums[j] = list1[j]\n",
    "        \n",
    "       \n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return nums\n",
    "        k %= n\n",
    "        if k==0:\n",
    "            return nums\n",
    "        lo, hi = 0, n-1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        lo, hi = 0, k-1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        lo, hi = k, n - 1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums) \n",
    "        if n <= 1:\n",
    "            nums = nums\n",
    "        else:\n",
    "            k %= n\n",
    "        \n",
    "            nums[n:] = nums\n",
    "            del nums[n*2-k:]\n",
    "            del nums[0:n-k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k%len(nums)):\n",
    "            nums.insert(0,nums.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k):\n",
    "            last = nums.pop(-1)\n",
    "            nums.insert(0, last)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 1 or k == 0:\n",
    "            return\n",
    "\n",
    "        kms = []\n",
    "        tag = n - k \n",
    "        for i in range(n):\n",
    "            flag = (tag + i) % n\n",
    "            kms.append(nums[flag])\n",
    "        \n",
    "        for i in range(n):\n",
    "            nums[i] = kms[i]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        k%=n\n",
    "        nums[:]=nums[n-k:]+nums[:n-k]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k):\n",
    "            nums.insert(0,nums[-1])\n",
    "            del nums[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)    # 处理长度大于数组长度的情况\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k %= len(nums)\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums1 = nums.copy()\n",
    "        for i in range(len(nums)):\n",
    "            j = (i+k)%len(nums)\n",
    "            nums[j] = nums1[i]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
